'''
    骑士之旅：在一个棋盘上，一个人只能像象棋里的马一样行走。我们需要他能遍历棋盘上的所有节点
    思路：我们先建立一个图，8*8的棋盘中图应该含有64个节点，然后根据每个顶点的行走方式确定其邻接顶点。
        使用深度优先搜索的方法，找到一条能够到达结尾的出路。
        进一步考虑能够优化深度优先搜索方法。
'''
import graph
from graph import Graph,Vertex  # 顶点和图类

# 创建图
def knightGraph(bdSize):    # 传入参数为棋盘行列大小
    ktGraph = Graph()

    for row in range(bdSize):   # 行
        for col in range(bdSize):   # 列
            nodeId = PosToNodeId(row,col,bdSize)    # nodeId：0-63
            newPositions = genLegalMoves(row,col,bdSize)    # 行列能够直连到的位置
            for i in newPositions:
                nid = PosToNodeId(i[0],i[1],bdSize) # 找到相连的顶点ID
                ktGraph.addEdge(nodeId,nid)
    return ktGraph


def PosToNodeId(row,col,bdSize):    # 行列坐标到节点ID的映射
    return row * bdSize + col

def genLegalMoves(x,y,bdSize):
    newMoves = []
    moveOffsets = [(-1,-2),(-1,2),(1,-2),(1,2),(2,1),(2,-1),(-2,1),(-2,-1)]
    for i in moveOffsets:
        newX = x + i[0]
        newY = y + i[1]
        if legalCoord(newX,newY,bdSize):
            newMoves.append((newX,newY))
    return newMoves

def legalCoord(x,y,bdSize):
    if (x >= 0 and x < bdSize) and (y >= 0 and y < bdSize):
        return True
    else:
        return False


# n: 当前深度 path: 到此为止访问的顶点列表，u：当前节点 limit：需要访问的深度
# 深度优先搜索
# 步骤
'''
    1. 当前节点颜色变为white且节点加入path列表
    2. 获取当前节点的相连节点。返回一个列表
    3. 依次获取该列表的元素，如果没有终止且列表节点颜色为白色，对该列表进行深度优先搜索
    4. 如果列表遍历完但是没有完成，说明该方向是个死胡同，栈中去除这个节点且该节点设置为white，因为其他情况还要用到这个节点。
'''
def knightTour(n,path,u,limit):
    u.setColor('gray')
    path.append(u)
    # print(u.getId())
    if n < limit:
        nbrList = list(u.getConnections())  #
        # nbrList = orderByAvail(u)
        i = 0
        done = False
        while i < len(nbrList) and not done:
            if nbrList[i].getColor() == 'white':
                done = knightTour(n+1,path,nbrList[i],limit)
            i = i + 1

        # 弄完了还没有done，需要回溯
        if not done:
            path.pop()
            u.setColor('white')

    else:
        done = True
        print([p.getId() for p in path])
    return done

'''
# 上述的深度优先搜索方法复杂度太高，其复杂度可能随着图深度的增加呈现指数增长，现在考虑优化方式
使用具有最多可用移动的顶点作为路径上的下一个顶点的问题是，它倾向于让骑士在游览中早访问中间的方格。
当这种情况发生时，骑士很容易陷入板的一侧，在那里它不能到达在板的另一侧的未访问的方格。另一方面，
访问具有最少可用移动的方块首先推动骑士访问围绕板的边缘的方块。这确保了骑士能够尽早地访问难以到达的角落，
并且只有在必要时才使用中间的方块跳过棋盘。利用这种知识加速算法被称为启发式。
也就是说，我们考虑改变他的遍历方式来改变复杂度，我们只是想找到一条路径而不是所有路径。所以这种方式能最快的找到路径
'''
def orderByAvail(n):
    resList = []    # 存储元

    for v in n.getConnections():
        if v.getColor() == 'white':
            c = 0
            for w in v.getConnections():
                if w.getColor() == 'white':
                    c = c + 1   # 相当于统计v的邻居数量，我们按照邻居数量从小到大排序

            resList.append((c,v))   # 得到n相连的节点及其节点所连的节点
    resList.sort(key=lambda x:x[0])
    return [y[1] for y in resList]

if __name__ == '__main__':
    knightGraph = knightGraph(8) # 创建图 63位
    u = knightGraph.getVertex(0)
    # for v in knightGraph: # 这个返回的是键值：顶点
    #     for w in v.getConnections():
    #         print('(%s,%s,%s)' %(v.getId(),w.getId(),v.connectTo[w]))
    for w in u.getConnections():
        print('(%s,%s,%s)' %(u.getId(),w.getId(),u.connectTo[w]))
    path = []
    knightTour(0,path,u,63)

    # 经过我的事实验证，采用启发式可以很快的运算完成，而采用一般方法则需要计算很久得到结果。二者会得到相同的结果。